home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6108 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.0 KB
  1. Path: po.CWRU.Edu!mab22
  2. From: mab22@po.CWRU.Edu (Michael A. Balfour)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 22 Feb 1996 19:37:19 GMT
  6. Organization: Case Western Reserve University, Cleveland, OH (USA)
  7. Message-ID: <4giglf$99h@madeline.INS.CWRU.Edu>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu> <harmon.824680556@pegasus.montclair.edu>
  9. Reply-To: mab22@po.CWRU.Edu (Michael A. Balfour)
  10. NNTP-Posting-Host: kanga.ins.cwru.edu
  11.  
  12.  
  13. In a previous article, harmon@pegasus.montclair.edu (Derek Harmon) says:
  14.  
  15. >anh@kuhub.cc.ukans.edu writes:
  16. >>This is not a quite a C problem. But since the implementation will be in 
  17. >>C anyway.
  18. >
  19. >>Another way is to simply assign a id to a word and store the word in a 
  20. >>binary search tree, and therefore, it is relatively fast to make sure 
  21. >>each word has an unique id. But I think it is still to slow. We are 
  22. >>talking about a possible 200,000+ words.
  23. > 
  24. >   How balanced the tree would be depends on either the order of input, or
  25. >the tree's self-balancing of itself which makes input longer, but logarith-
  26. >mically lowers the bound on search time.  But we are talking about more than
  27. >200,000 words here, and that is where the problem occurs.  If the max length
  28. >of these strings is 32 characters, then we are talking about roughly 7.3 x
  29. >10^43 different strings.  That will not fit into a 64-bit long.  :)
  30. >
  31.  
  32. Another possibility to approach is a hash table.  A method I've been
  33. examining for doing searches on strings instantly without even storing
  34. the list of strings involves minimal perfect hash functions.  The
  35. general idea is that every string you're using as input hashes to a
  36. specific unique value.  Using this technique, you just hash the string
  37. to be searched on, and use the hash value to index into an array of
  38. return values.
  39.  
  40. A good paper on the topic can be found at ftp.cs.uq.oz.au.  The paper is
  41. "An optimal algorithm for generating minimal perfect hash functions"
  42. written by Zbigniew Czech, George Havas, and Bohdan Majewski.
  43.  
  44. Mike Balfour 
  45. >   The formula you give above will give all those strings distinct id nums,   
  46. >if you have knowledge of the probability of occurence of symbols from that
  47. >language, you can shift the probability of smaller id num size (there will
  48. >still be large id nums) for a random sampling of those strings.  However,
  49. >if symbols have equal probabilities of selection, finnagling of the formula
  50. >won't add any advantage.  If it were possible, the world would be a path to
  51. >your door for an infinite data compression method.
  52. >
  53. >                                                    -- Stone
  54. >--
  55. ># Derek Harmon (aka Stonelight)    harmon@pegasus.montclair.edu
  56. ># - Computer Science Undergrad, Montclair State University, NJ
  57. ># - My views are my own, nobody else is this creative.  3;)>
  58. >... Recursive. adj., see Recursive.
  59. >
  60. >
  61.  
  62. -- 
  63. ----------------------------------+--------------------------------
  64. Mike Balfour, Partner             | BS/MS Graduate - ECMP
  65. Overload Engineering              | Case Western Reserve University
  66. "New Ideas for a Brighter Future" | Cleveland, OH
  67.